/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at https://interview.codeplex.com/team/views.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

// Problem:
//     Giving an integer array, e.g. { 15, 7, 12, 6, 14, 13, 9, 11 }, find the consecutive sub items
//     within the array, in this example, return 5: { 11, 12, 13, 14, 15 }
//
// Author: everyday (weijie.he@live.com)
//

#include <iostream>
#include <string>
#include <map>
using namespace std;

int find_longest_consecutive_items(int *list, int size) {
    map<int, int> mapping;
    int max = 0;
    // The start point for the longest chain
    int start = 0;

    for (int i=0; i<size; i++) {
        if (mapping.find(list[i]) == mapping.end()) {
            int cur = list[i];
            // Set current position as the start point for this potential longest chain
            int cur_start = cur;
            mapping.insert(make_pair(cur, 1));

            map<int, int>::iterator prev = mapping.find(cur - 1);
            map<int, int>::iterator next = mapping.find(cur + 1);

            if (prev != mapping.end()) {
                // If previous number exists, increase current consecutive count
                mapping[cur] = prev->second + 1;
            }

            if (next != mapping.end()) {
                // Update the last one in the chain with the consecutive count from the one before current position
                int last = next->first + next->second - 1;
                mapping[last] = mapping[cur] = mapping[cur] + mapping[last];
            }

            if (prev != mapping.end()) {
                // Update the first one in the chain with the consecutive count from the one after current position
                int first = prev->first - prev->second + 1;
                mapping[first] = mapping[cur];

                // Use the first one as the start point for the whole chain
                cur_start = first;
            }

            if (mapping[cur_start] > max) {
                start = cur_start;
                max = mapping[cur_start];
            }
        }
    }

    cout << "Longest consecutive items:";
    for (int i=0; i<max; i++) {
        cout << " " << start + i;
    }
    cout << endl;

    return max;
}

int main(int argc, char* argv[])
{
    int v[] = {16,12,14,15,13,7,4,8,11,0};
    cout << "Count: " << find_longest_consecutive_items(v, sizeof(v) / sizeof(int)) << endl;

    return 0;
}

